package strategy.demo;

public class MergeSortStrategy implements SortStrategy {
    @Override
    public void sort(int[] arr) {


        buf = new int[arr.length];
        sort(arr, 0, arr.length - 1);

    }

    //T(n)=T(n/2)+T(n/2)+O(n) =>T(n)=O(nlogn)
    public void sort(int[] a, int left, int right) {
        if (left >= right) return;
        int mid = (right + left) / 2;
        //a[left,mid]  and a[mid+1,right]
        sort(a, left, mid);
        sort(a, mid + 1, right);
        int i = left, j = mid + 1, k = left;
        while (i <= mid && j <= right) {
            if (a[i] <= a[j]) {
                buf[k++] = a[i++];
            } else {
                buf[k++] = a[j++];
            }
        }
        while (i <= mid) buf[k++] = a[i++];
        while (j <= right) buf[k++] = a[j++];
        for (int x = left; x <= right; x++) a[x] = buf[x];

    }

    int[] buf;
}
